package com.situ.huffman;

import java.util.HashMap;
import java.util.LinkedHashMap;

import java.util.Map;

public class HuffmanTree extends BinaryTree<HuffmanValue> {

	private Map<Character, String> codes = new LinkedHashMap();

	public HuffmanTree(String text) {

		// Map记录每个字符出现的次数
		Map<Character, Integer> counts = new HashMap<>();

		for (int i = 0; i < text.length(); i++) {
			// 取出下标为i的字符
			Character c = text.charAt(i);

			// 判断是否已经统计过
			if (counts.containsKey(c)) {
				// 已经统计过
				Integer count = counts.get(c);
				count++;
				counts.put(c, count);
			} else {
				// 没有统计过
				counts.put(c, 1);
			}
		}
		// System.out.println(counts);

		// 遍历统计到所有的字符
		Node<HuffmanValue>[] nodes = new Node[counts.size()];

		int i = 0;
		for (Character c : counts.keySet()) {
			Node<HuffmanValue> newNode = new Node<HuffmanValue>();
			HuffmanValue value = new HuffmanValue(c, counts.get(c));
			newNode.setData(value);
			nodes[i++] = newNode;
		}
		// 调用生成树的方法
		generate(nodes, nodes.length);

		// 生成编码
		generateCode(this.getRoot(), "");
	}

	public String toCode(String text) {
		// 可变字符串，可以提高字符串拼接的执行效率
		StringBuilder builder = new StringBuilder();
		for (int i = 0; i < text.length(); i++) {
			Character c = text.charAt(i);
			// 从map中查找字符对应的huffman编码
			String code = codes.get(c);
			builder.append(code);
		}
		return builder.toString();
	}

	public String toText(String code) {
		// 可变字符串，可以提高字符串拼接的执行效率
		StringBuilder codebuilder = new StringBuilder(code);
		StringBuilder textbuilder = new StringBuilder();
		while (codebuilder.length() > 0) {
			Character c = checkCode(codebuilder);
			textbuilder.append(c);
		}
		return textbuilder.toString();
	}

	// 从二进制编码上取出第一个字符
	public Character checkCode(StringBuilder codebuilder) {
		// 遍历map
		for (Character c : codes.keySet()) {
			if (codebuilder.toString().startsWith(codes.get(c))) {
				// 删除已经找到的二进制序列
				codebuilder.delete(0, codes.get(c).length());
				return c;
			}
		}
		return null;
	}

	public HuffmanTree(HuffmanValue[] datas) {
		// datas 保存的是节点的值的集合
		// 集合，保存节点的
		Node<HuffmanValue>[] nodes = new Node[datas.length];
		for (int i = 0; i < datas.length; i++) {
			nodes[i] = new Node<HuffmanValue>();
			nodes[i].setData(datas[i]);
		}
		// 调用生成树的方法
		generate(nodes, datas.length);

		// 生成编码
		generateCode(this.getRoot(), "");
	}

	private void generateCode(Node<HuffmanValue> node, String code) {
		if (node.getLeft() == null && node.getRight() == null) {
			System.out.println("叶子节点" + node.getData().getCharacter() + " code:[" + code+"]");
			// 将字符和huffman编码保存到map中
			codes.put(node.getData().getCharacter(), code);
		} else {
			// 不是叶子节点
			// 递归遍历左子树
			generateCode(node.getLeft(), code + "0");
			// 递归遍历右子树
			generateCode(node.getRight(), code + "1");
		}

	}

	private void generate(Node<HuffmanValue>[] nodes, int length) {
		if (length == 1) {
			this.setRoot(nodes[0]);
		} else {
			// 1、获取元素值最小的两个元素
			Node<HuffmanValue> left = getMin(nodes, length--);
			Node<HuffmanValue> right = getMin(nodes, length--);

			// 2、构造这两个节点的父节点
			Node<HuffmanValue> newNode = new Node<>();
			newNode.setLeft(left);
			newNode.setRight(right);

			// 设置父节点（新节点）的数值域
			HuffmanValue value = new HuffmanValue();
			// 设置数值域的权重
			value.setWeight(left.getData().getWeight() + right.getData().getWeight());
			// 设置数值域数据
			newNode.setData(value);

			// 3、将新节点添加进节点集合
			nodes[length++] = newNode;

			// 4、递归调用
			generate(nodes, length);
		}

	}

	private Node<HuffmanValue> getMin(Node<HuffmanValue>[] nodes, int length) {
		int minIndex = 0;
		for (int i = 1; i < length; i++) {
			if (nodes[i].getData().getWeight() < nodes[minIndex].getData().getWeight()) {
				minIndex = i;
			}
		}
		// 取出此节点
		Node<HuffmanValue> minNode = nodes[minIndex];

		// 后边节点前移
		for (int i = minIndex; i < length - 1; i++) {
			nodes[i] = nodes[i + 1];
		}
		return minNode;
	}
}

class HuffmanValue {
	// 数据
	private Character character;
	// 权重
	private int weight;

	public HuffmanValue() {
	}

	public HuffmanValue(Character character, int weight) {
		this.character = character;
		this.weight = weight;
	}

	public Character getCharacter() {
		return character;
	}

	public void setCharacter(Character character) {
		this.character = character;
	}

	public int getWeight() {
		return weight;
	}

	public void setWeight(int weight) {
		this.weight = weight;
	}

}